package 两个链表中的第一个公共节点;

//题目描述
//输入两个链表，找出它们的第一个公共结点。
// （注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）
public class Solution
{
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2)
    {
        //先找到尾结点，再往前找，第一个不相等的前一个就是，单向链表，只有next
        //比较长度法，长的那个链表先走多出来的那几步，然后同时到达第一个公共节点
        int len1=GetLength(pHead1);
        int len2=GetLength(pHead2);
        ListNode listNodelong=null;
        ListNode listNodeshort=null;

        int x=Math.abs(len1-len2);//差值
        if (len1>len2)
        {
            listNodelong=pHead1;
            listNodeshort=pHead2;
        }
        else
        {
            listNodelong=pHead2;
            listNodeshort=pHead1;
        }
        for (int i = 0; i < x; i++)//走几步
        {
            listNodelong=listNodelong.next;
        }
//        for (int i = 0; i < Math.min(len1, len2); i++)
//        {
//            //第一个相等的公共节点就是所求
//            if (listNodelong==listNodeshort)
//                return listNodelong;
//
//            listNodelong=listNodelong.next;
//            listNodeshort=listNodeshort.next;
//        }
//        return null;
        //另一种return方法
        while ((listNodelong!=null)&&(listNodeshort!=null)//跳出条件
                &&(listNodelong!=listNodeshort))
        {
            listNodelong=listNodelong.next;
            listNodeshort=listNodeshort.next;
        }
        ListNode firstCommonNode=listNodelong;
        return firstCommonNode;
    }
   public int GetLength(ListNode pHead)
   {
       int length=0;
       while (pHead!=null)
       {
           pHead=pHead.next;
           length++;
       }
       return length;
   }
}
